﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _8QueensProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            QueensProblem.ArrangeQueens();
            QueensProblem.Display();
            Console.ReadKey();
        }
    }
    class QueensProblem
    {
        private static int[] temp = new int[8];
        private static string[,] chess = new string[8,8];
        static QueensProblem()
        {
            for (int i = 0; i < chess.GetLength(0); i++)
            {
                temp[i] = -1;
            }

            for (int i = 0; i < chess.GetLength(0); i++)
            {
                for (int j = temp[i] + 1; j < chess.GetLength(0); j++)
                {
                    chess[i, j] = "_ ";
                }
            }            
        }

        public static void ArrangeQueens()
        {
            for (int i = 0; i < chess.GetLength(0); i++)
            {
                int j;
                for (j = temp[i] + 1; j < chess.GetLength(0); j++)
                {                    
                    if(temp[i] != -1)
                        chess[i, temp[i]] = "_ ";
                    temp[i] = -1;
                    if (IsCorrectMove(i, j))
                    {
                        temp[i] = j;
                        chess[i, j] = "x ";
                        break;
                    }
                }
                if (j == 8)
                {
                    if(temp[i] != -1)
                        chess[i, temp[i]] = "_ ";
                    temp[i] = -1;
                    i-=2;
                }
            }
        }


        private static bool IsCorrectMove(int row, int j)
        {
            int i = 0;
            while (temp[i] != -1)
            {
                if (IsVerticalClash(j, temp[i]))
                    return false;
                if (IsDiagonalClash(row, j, i, temp[i]))
                    return false;
                i++;
            }
            return true;
        }

        private static bool IsDiagonalClash(int i, int j, int p, int q)
        {
            if (j - i == q - p || i - j == p - q)
                return true;
            else if (i + j == p + q)
                return true;
            return false;
        }

        private static bool IsVerticalClash(int j, int p)
        {
            if (j == p)
                return true;
            return false;
        }
        public static void Display()
        {
            for (int i = 0; i < chess.GetLength(0); i++)
            {
                for (int j = 0; j < chess.GetLength(0); j++)
                {
                    Console.Write(chess[i, j]);
                }
                Console.WriteLine();
            }
        }
    }
}
